MCOI R4 A solution

简要题解

Part1 预处理子集最大团

定义：$f(S)$ 是集合 $S$ 的最大团大小，$r(x)$ 是点 $x$ 的邻居的集合

对于任意一个 $S\neq \varnothing$，取任意 $x\in S$，考虑 $x$ 是否在最大团中，可以得到转移：$f(S)=\max(1+f(S\cap r(x)),f(S-\{x\}))$

状压从小到大枚举 $S$，dp 计算即可

注意到我们只需要对每个子集大小分别求出子集最大团的和

所以数组可以开大小 $2^{n-1}$ 的char类型，因为后 $2^{n-1}$ 个值不会再次被用到了

Part2 计算贡献

如果在第 $y$ 回合结束后剩下一个大小为 $x$ 的子集，包含这种状态的方案数应该是 $y^{n-x}((k-y+1)^x-(k-y)^x)$

也就是，考虑每个点是在哪一回合删除的

由于 $x$ 的范围只有 $[0,n]$ 所以可以枚举，所以要求的就是 $\sum_{y=1}^k y^{n-x}((k-y+1)^x-(k-y)^x)$

这是个关于 $k$ 的 $n+1$ 次多项式，暴力求 $n+2$ 个点值然后拉格朗日插值即可

Part3 卡常

这个……看标程吧，最大点 356ms，还挺快的（初代标程最大点 700+ms，
被我优化了一半常数，我认为有必要区分一下）

标程长这样，欢迎抄题解

#include <cstdio>
#include <algorithm>
#define N 28
#define P 1000000007
int n, m, k, G[N], s[N+1]; char a[1<<(N-1)];
int inv[N+2], pow[N+2][N+1];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[x] |= 1 << y;
		G[y] |= 1 << x;
	}
	for (int x = 1, t = 1, d = 0; ; x++) {
		if (x & (t<<1)) {t <<= 1; if (++d == n-1) break; }
		a[x] = std::max(a[x^t], char(a[x&G[d]]+1));
		int c = __builtin_popcount(x); s[c] += a[x];
		s[c+1] += std::max(int(a[x]), a[x&G[n-1]]+1);
	}
	s[1]++;
	pow[0][0] = inv[1] = 1;
	for (int i = 1; i <= n+1; i++) {
		pow[i][0] = 1;
		for (int j = 1; j <= n; j++)
			pow[i][j] = 1ll * pow[i][j-1] * i % P;
	}
	for (int i = 2; i <= n+1; i++)
		inv[i] = 1ll * (P-P/i) * inv[P%i] % P;
	int ans = 0;
	for (int g = 1; g <= n; g++) {
		for (int i = 1; i <= n+1; i++) {
			int y = 0;
			for (int j = 1; j <= i; j++)
				y = (1ll * pow[j][n-g] * (pow[i-j+1][g] - pow[i-j][g] + P) + y) % P;
			for (int j = 0; j <= n+1; j++) if (i != j)
				y = 1ll * y * (k-j+P) % P * (i>j?inv[i-j]:P-inv[j-i]) % P;
			ans = (1ll * y * s[g] + ans) % P;
		}
	}
	printf("%d\n", ans);
}